|
Jack R. Edmonds (born April 5, 1934) is an American computer scientist, regarded as one of the most important contributors to the field of combinatorial optimization. He was the recipient of the 1985 John von Neumann Theory Prize. ==Research== A break through contribution of Edmonds is defining the concept of polynomial time characterising the difference between a practical and an impractical algorithm. Another of Edmonds' earliest and most notable contributions is the blossom algorithm for constructing maximum matchings on graphs, discovered in 1961, and published in 1965.〔 〕 This was the first polynomial-time algorithm for maximum matching in graphs. Its generalization to weighted graphs〔 〕 was a conceptual breakthrough in the usage of linear programming ideas in combinatorial optimization. It sealed in the importance of there being proofs/witnesses that the answer for an instance is yes and there being proofs/witnesses that the answer for an instance is no. Additional landmark work of Edmonds is in the area of matroids. He found a polyhedral description for all spanning trees of a graph, and more generally for all independent sets of a matroid.〔 〕 Building on this, as a novel application of linear programming to discrete mathematics, he proved the matroid intersection theorem, a very general min-max combinatorial theorem〔.〕〔 which, in modern terms, showed that the matroid intersection problem lay in both NP and co-NP. Edmonds is well known for his theorems on max-weight branching algorithms〔 〕 and packing edge-disjoint branchings〔 〕 and his work with Richard Karp on faster flow algorithms. The Edmonds–Gallai decomposition theorem describes finite graphs from the point of view of matchings. He introduced polymatroids,〔 submodular flows with Richard Giles,〔 〕 and the terms clutter and blocker in the study of hypergraphs.〔 A recurring theme in his work〔 〕 is to seek algorithms whose time complexity is polynomially bounded by their input size and bit-complexity〔 (see the Cobham–Edmonds thesis). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Jack Edmonds」の詳細全文を読む スポンサード リンク
|